package class06

import "math"

/*
	求 字符串 如果分割为回文串，返回最少的回文串分割的数量
	如：”aba12321“ 返回 2，最少可以分割为 ”aba”， “12321“
	思路：
		从左到右的尝试模型，递归函数的设计
		MinPartsProcess(s, i) ：返回字符串中 i...N-1， 最少的回文串分割数量
		可能性分析：
			i...N-1 的回文串拆分可能性：
			1. i 字符串作为分割点，则当前的结果为：MinPartsProcess(s, i+1)+1
			2. i..i+1 字符串作为分割点，前提是i...i+1是回文串，结果为MinPartsProcess(s, i+2)+1
			3  遍历至i...N-1作为分割点 MinPartsProcess(s, N)+1
		优化：
			判断是否是回文串，使用dp表做优化，使用范围尝试模型，以字符串的两个维度作为尝试
			f(s, i, j) = s[i] == s[j] && f(s, i+1, j-1)
			对应dp表, 只用填上半部分，因为，下半部分无意义
				0 1 2 3 4 5
			0	? ? ? ? ? ?
			1	  ? ? ? ? ?
			2	    ? ? ? ?
			3		  ? ? ?
			4			? ?
			5			  ?
			根据base case 先填写对角线以及对角线上面的一个对角线，然后再填写其余的位置。

*/
func MinParts(s string) int {
	isP := GetIsP(s)
	N := len(s)
	dp := make([]int, N+1)
	dp[N] = 0
	for i:=0; i<N; i++ {
		dp[i] = math.MaxInt
	}
	for i:=N-1; i>=0; i-- {
		for end:=i; end<N; end++ {
			if isP[i][end] {
				dp[i] = min(dp[i], dp[end+1]+1)
			}
		}
	}
	return dp[0]
}

func min(a, b int) int {
	if a > b{
		return b
	}
	return a
}

func GetIsP(s string) [][]bool {
	N := len(s) // 字符串长度N
	dp := make([][]bool, N)
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]bool, N)
	}
	// 填写对角线
	for i:=0; i<N; i++ {
		dp[i][i] = true
	}
	// 填写对角线上面的部分
	//	0 1 2 3 4 5
	//0	? ? ? ? ? ?
	//1	  ? ? ? ? ?
	//2	    ? ? ? ?
	//3		  ? ? ?
	//4			? ?
	//5			  ?
	for i:=0; i<N-1; i++ {
		dp[i][i+1] = s[i] == s[i+1]
	}
	// 填写剩下的对角线
	diagonal := 2
	var row, col int
	for diagonal < N {
		row, col = 0, diagonal
		for col < N {
			dp[row][col] = s[row] == s[col] && dp[row+1][col-1]
			row++
			col++
		}
		diagonal++
	}
	return dp
}
